package sort;

import java.util.Arrays;

/**
 * @author LLing
 * @className QuickSort
 * @description: 快速排序的实现
 * @date 2021/12/12 15:07
 */
public class QuickSort {


    /**
     * 递归+双边循环实现快速排序
     * @param startIndex 起始位置
     * @param endIndex 结束位置
     * @param array 排序的数组
     */
    public static void quickSort(int startIndex,int endIndex,int [] array){

        //递归结束条件
        if (startIndex>=endIndex){
            return;
        }
        //双边循环
//        int pivotIndex  =douPartition(array,startIndex,endIndex);
//        quickSort(startIndex, pivotIndex-1, array);

        //单边循环
        int pivotIndex  =singlePartition(array,startIndex,endIndex);
        quickSort(startIndex, pivotIndex-1, array);
        quickSort(pivotIndex+1,endIndex,array);

    }



    /**
     * 分治（双边循环）
     * @param array 待排序的数组
     * @param startIndex 起始位置
     * @param endIndex 结束位置
     * @return
     */
    private static int douPartition(int[] array, int startIndex, int endIndex) {

        //取第1个位置值为基准元素，也可以任意取
        int pivot = array[startIndex];
        int left = startIndex;
        int right = endIndex;

        //控制right指针左移
        while (left != right){
            while (right>left && pivot<array[right]){
                right--;
            }
            //控制left指针右移动
            while (left <right && array[left]<=pivot){
                left++;
            }

            //交换left和right位置的值
            if (left<right){
                int temp = array[left];
                array[left]  = array[right];
                array[right]  = temp;
            }
        }


        //pivot与指针重合交换
        array[startIndex] = array[left];
        array[left] = pivot;
        return left;
    }


    /**
     * 分治（单边循环）
     * @param array
     * @param startIndex
     * @param endIndex
     */
    public static int singlePartition(int[] array,int startIndex,int endIndex){
        //取第一个位置元素为基准元素
        int pivot = array[startIndex];
        int mark = startIndex;
        for (int i = startIndex+1; i <=endIndex; i++) {
            if (array[i]<pivot){
                mark++;
                int p = array[mark];
                array[mark] = array[i];
                array[i] = p;
            }
        }

        array[startIndex]  = array[mark];
        array[mark] = pivot;
        return mark;

    }

    public static void main(String[] args) {
        int [] array = new int[]{4,7,3,5,6,2,8,1};
        quickSort(0,array.length-1,array);
        System.out.println(Arrays.toString(array));


    }
}
